package Tree;

/**
 * @author Liaorun
 */
public class WhereCanReachNumber {

    /**
     * 暴力方法为了测试
     *
     * @param map 一个二维矩阵地图， 上面有 . U D L R 5种地形, . 可以随便走，其他地形只能按照规定的路径走
     * @return 随机选择一个点可以到达目的地的点的集合
     */
    public static int number1(char[][] map) {

        int ans = 0;
        int n = map.length;
        int m = map[0].length;

        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (dfs(map, i, j, visited)) {
                    ans++;
                }
            }
        }

        return ans;
    }

    private static boolean dfs(char[][] map, int i, int j, boolean[][] visited) {

        if (i < 0 || i == map.length || j < 0 || j == map[0].length || visited[i][j] || map[i][j] == '.') {
            return false;
        }

        // 代表当前节点已经来过
        visited[i][j] = true;

        boolean ans = false;

        if (map[i][j] == 'O') {
            // 到达了目的地，直接返回true
            ans = true;
        } else {
            if (map[i][j] == 'U') {
                // 向上一个点探索
                ans = dfs(map, i - 1, j, visited);
            } else if (map[i][j] == 'D') {
                // 向下一个点探索
                ans = dfs(map, i + 1, j, visited);
            } else if (map[i][j] == 'L') {
                // 向左边一个点探索
                ans = dfs(map, i, j - 1, visited);
            } else if (map[i][j] == 'R') {
                // 向右边一个点探索
                ans = dfs(map, i, j + 1, visited);
            } else {
                // 当前地形没有传送带，上下左右都要探索
                ans = dfs(map, i - 1, j, visited) || dfs(map, i + 1, j, visited) || dfs(map, i, j - 1, visited) || dfs(map, i, j + 1, visited);
            }
        }

        visited[i][j] = false;

        return ans;
    }

    /**
     * 时间复杂度更小的解法
     *
     * @param map 一个二维矩阵地图， 上面有 . U D L R 5种地形, . 可以随便走，其他地形只能按照规定的路径走
     * @return 随机选择一个点可以到达目的地的点的集合
     */
    public static int number2(char[][] map) {
        int n = map.length;
        int m = map[0].length;

        // 记录到达过的点，防止在宽度优先遍历的过程中重复遍历
        boolean[][] visited = new boolean[n][m];

        // queue[i] = {行坐标，列坐标}
        int[][] queue = new int[n * m][2];

        int l = 0;
        int r = 0;
        int ans = 0;

        // O 在那，目的地
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'O') {
                    visited[i][j] = true;
                    queue[r][0] = i;
                    queue[r++][1] = j;
                    break;
                }
            }
        }

        // [] [] [] []
        // l ...... r
        // 队列里还有位置
        while (l < r) {
            ans++;
            int[] cur = queue[l++];
            int row = cur[0];
            int col = cur[1];
            // 上面有点 && 上面的点没有到过 && (点里是D字符 || 点里是.字符)
            if (row - 1 >= 0 && !visited[row - 1][col] && (map[row - 1][col] == 'D' || map[row - 1][col] == '.')) {
                visited[row - 1][col] = true;
                queue[r++][0] = row - 1;
                queue[r++][1] = col;
            }

            // 下面有点 && 下面的点没有到过 && (点里是U字符 || 点里是.字符)
            if (row + 1 >= 0 && !visited[row + 1][col] && (map[row + 1][col] == 'U' || map[row + 1][col] == '.')) {
                visited[row + 1][col] = true;
                queue[r++][0] = row + 1;
                queue[r++][1] = col;
            }
            // 左边有点 && 左边的点没有到过 && (点里是R字符 || 点里是.字符)
            if (col - 1 >= 0 && !visited[row][col - 1] && (map[row][col - 1] == 'R' || map[row][col - 1] == '.')) {
                visited[row][col - 1] = true;
                queue[r++][0] = row;
                queue[r++][1] = col - 1;
            }
            // 右边有点 && 右边的点没有到过 && (点里是L字符 || 点里是.字符)
            if (col + 1 < map[row].length && !visited[row][col + 1] && (map[row][col + 1] == 'L' || map[row][col + 1] == '.')) {
                visited[row][col + 1] = true;
                queue[r++][0] = row;
                queue[r++][1] = col + 1;
            }

        }

        return ans;
    }
}
